1. Field of the Invention
This invention relates generally to the field of digital computers and more particularly to the area of memory control within a computer. More specifically it relates to a synonym detection and handling mechanism for caches in a virtual storage system.
2. Description of the Prior Art
In a data processing system with a storage hierarchy, selected lines of data in a main storage are copied in a local high speed buffer, often called a cache, for fast access by a CPU. Whenever the processor requests new data, the system first checks the cache to determine whether the data is available in the cache; and if it is, the data is quickly provided to the processor. If the data is not available in the cache, the data is retrieved more slowly from the main memory.
Caches in current systems are typically based on the concept of "set associativity", wherein a CPU requestor directly addresses a cache directory slot (called a class) having several entries and associatively searches all entries in one class in parallel to determine if the addressed class has an address matching the request address. A set-associative cache is a compromise between a fully associative cache, in which any block of main storage may map into any position in the cache, and a directly addressed cache, where each main storage address can map into only one location in the cache. Fully associative caches have the liability of lengthy directory search time and an elaborate replacement (LRU) mechanism. Non-associatively addressed caches are the simplest to implement in terms of hardware, but yield significantly lower performance than the other two schemes due to increased overwriting of entries.
As the size of the preferred set-associative cache increases, either (1) the address range used to access the cache increases, or (2) the degree of set-associativity must be increased, or (3) both the set-associativity and address range are increased. An increase in the set associativity, however, takes either extra time or excessive hardware to examine all sets in the addressed class. Also, available IC packaging technology for cache directories does not lend itself a substantial increase in set associativity. Accordingly, cost constraints prefer that the cache directory size be increased by increasing the directory address range (i.e. number of classes). However, as the number of classes in the cache directory is increased, eventually the directory address bits taken from a requesting virtual address must expand past the high-order end of its non-translatable field (i.e. the D field) of the virtual address and into the translatable field (i.e. PX field) of the virtual address. The so-called cache synonym problem occurs when the cache address uses bits from the translatable field of the logical address. A cache synonym exists when the data required by a requesting logical address is available in a cache class different from the class addressed by the request. Synonyms may for example be caused by (1) requests which switch between virtual and real addresses for the same data, or (2) by one user addressing a line of data with one virtual address and another user addressing the same line with a different virtual address which locates a different class in the cache.
U.S. Pat. No. 3,723,976 to J. A. Alvarez at al, issued Mar. 27, 1973 and assigned to the assignee of the present application, shows a memory system with logical and real addressing in a multi-processing environment. Each processor has associated with it a cache. Means are provided for the cache to retain a modified copy of data. The contents of the cache may be accessed by a logical address, i.e. either a real or virtual address. A dynamic address translation directory (i.e. DLAT) contains translated logical addresses. A cache fetch directory is provided to keep track of the data in the cache. The cache fetch directory entries are addressed by bits from both translatable and non-translatable portions of the desired data address. Means are provided to insure that only one copy of data is maintained in the cache although it may be entered at any of several cache locations (i.e. principle or synonym location) dependent upon whether the virtual or real address last accessed the data. A cache hit/miss detection mechanism is such that when cross indexing is established for a new line being fetched, some lines in the cache will lose index pointers. They are marked invalid and they are cast out if changed. A synonym entry causes a miss and is therefore invalidated and may be cast out. If a synonym entry is the target of the current request, its miss causes it to be refetched from main storage and written back into the currently addressed partition (i.e. principle class) in the cache directory. The effect is to move a synonym to the principle class with a great loss in access time. The cache hit/miss detection mechanism described therein does not distinguish between a cache miss (where the requested data is not found in the cache), and a synonym hit (where the requested data is available in the cache at another location).
It has been proposed to perform synonym detection in a copy of a processor cache directory. This proposal also treats a synonym as a cache miss in the main directory. Synonym detection in the copy directory begins one or more cycles after the cache miss is first detected in the main directory. An additional cycle is taken in the copy directory for serially accessing each class which could possibly contain a synonym, e.g. three additional cycles for checking three classes which might contain a synonym line address. Such copy directory may also be used for other purposes, e.g. cross-interrogation of a request by another processor.
U.S. Pat. No. 3,761,881 to Anderson et al, issued Sept. 25, 1978 and assigned to the assignee of the present application, shows a translation storage scheme for virtual memory system. Both a main storage and a cache are real-address oriented. Current virtual-to-real address translations are retained in a translation lookaside table (TLAT), which is also sometimes called a DLAT. The cache directory uses real addresses to represent the data in the cache. Each CPU-provided virtual address accesses a class in the TLAT and a class in the cache directory. A virtual address stored in the accessed TLAT class is compared to the CPU virtual address. Also the translated real address in the accessed TLAT class is compared to each real address in the accessed cache directory class. If both the virtual and real address comparisons are equal, the data is accessed from a corresponding location in the cache.
U.S. Pat. No. 4,136,385 to Gannon et al, issued Jan. 23, 1979 and assigned to the assignee of the present application, shows a control means for handling common-segment DLAT synonyms. (The DLAT synonym problem is not related to the cache synonym problem.) The DLAT synonym control means in this patent is used with multiple virtual storage systems in which a common page has the same virtual address in plural address spaces. The control means eliminates plural entries for a common page in a translation lookaside buffer (DLAT) by providing a common indicator in each DLAT entry containing a common page address to eliminate associating the entry with any particular address space.
IBM Maintenance Library, "3033 Processor Complex, Theory of Operation/Diagram Manual" Volume 4, Processor Storage Control Function (PSCF) and Processor Storage, Form SY22-7004-0, pages 1.6.1 and 1.6.2 show and describe a large high speed buffer concept, in which a sixteen-way set associative cache is used to avoid the synonym problem by avoiding the use of any translatable bits of the processor request address in the cache directory address.